package MyLinkedList;

import MyException.MyIndexOutOfBoundsException;

public class MyLinkedList<T> {
    private static class ListNode<T> {
        public T value;
        private ListNode<T> next;
        private ListNode<T> prev;
        private ListNode() {

        }
        private ListNode(T value) {
            this.value = value;
        }
    }
    private ListNode<T> first;
    private ListNode<T> last;
    private int size;
    public MyLinkedList() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    public int size() {
        return this.size;
    }
    public boolean isEmpty() {
        return this.size == 0;
    }
    public void addFirst(T o) {
        ListNode<T> node = new ListNode<T>(o);
        if(this.isEmpty()) {
            this.first = node;
            this.last = node;
        }else {
            this.first.prev = node;
            node.next = this.first;
            this.first = node;
        }
        this.size++;
    }
    public void addLast(T o) {
        ListNode<T> node = new ListNode<T>(o);
        if(this.isEmpty()) {
            this.first = node;
            this.last = node;
        }else {
            this.last.next = node;
            node.prev = this.last;
            this.last = node;
        }
        this.size++;
    }
    public void add(T o) {
        this.addLast(o);
    }
    public void add(int index, T o) {
        if(index < 0 || index > this.size()) {
            throw new MyIndexOutOfBoundsException();
        }
        if(index == 0) {
            this.addFirst(o);
        }else if(index == this.size) {
            this.addLast(o);
        }else {
            ListNode<T> newNode = new ListNode<T>(o);
            ListNode<T> node = this.first;
            for(int i =0; i < index; i++) {
                node = node.next;
            }
            newNode.prev = node.prev;
            newNode.prev.next = newNode;
            newNode.next = node;
            node.prev = newNode;
            this.size++;
        }
    }
    public void clear() {
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    @Override
    public String toString() {
        StringBuilder str = new StringBuilder();
        ListNode<T> node = this.first;
        while(node != null) {
            str.append(node.value).append(" ");
            node = node.next;
        }
        return str.toString();
    }
    public T get(int index) {
        if(index < 0 || index >= this.size) {
            throw new MyIndexOutOfBoundsException();
        }
        ListNode<T> node = this.first;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        return (T)node.value;
    }
    public T set(int index, T o) {
        if(index >= this.size || index < 0) {
            throw new MyIndexOutOfBoundsException();
        }
        ListNode<T> node = this.first;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        Object oldValue = node.value;
        node.value = o;
        return (T)oldValue;
    }
    public T remove(int index) {
        if(index < 0 || index >= this.size) {
            throw new MyIndexOutOfBoundsException();
        }
        ListNode<T> node = this.first;
        for(int i = 0; i < index; i++) {
            node = node.next;
        }
        Object value = node.value;
        if(this.first == this.last) {
            this.first = null;
            this.last = null;
        } else if(node == this.first) {
            node.next.prev = null;
            this.first = node.next;
        }else if(node == this.last) {
            node.prev.next = null;
            this.last = node.prev;
        }else {
            node.next.prev = node.prev;
            node.prev.next =  node.next;
        }
        this.size--;
        return (T)value;
    }
    public void remove(T key) {
        ListNode<T> node = this.first;
        Object value = null;
        while(node != null) {
            if(node.value.equals(key)) {
                this.size--;
                if(this.first == this.last) {
                    this.first = null;
                    this.last = null;
                } else if(node == this.first) {
                    node.next.prev = null;
                    this.first = node.next;
                }else if(node == this.last) {
                    node.prev.next = null;
                    this.last = node.prev;
                    return ;
                }else {
                    node.next.prev = node.prev;
                    node.prev.next = node.next;
                }
            }
            node = node.next;
        }
    }
    public void removeAll(T key) {
        ListNode<T> node = this.first;
        while(node != null) {
            if(node.value.equals(key)) {
                this.size--;
                if(node == this.first) {
                    node.next.prev = null;
                    this.first = node.next;
                }else if(node == this.last) {
                    node.prev.next = null;
                    this.last = node.prev;
                    return;
                }else {
                    node.next.prev = node.prev;
                    node.prev.next = node.next;
                }
            }
            node = node.next;
        }
    }
    public void reverseDisPlay() {
        ListNode<T> node = this.last;
        while(node != null) {
            System.out.print(node.value + " ");
            node = node.prev;
        }
        System.out.println();
    }
}
